/*
* （该算法可以推广为如何使当前收益最大化）
* 黄金部队：挖矿的人数有限10人
* 每个金矿的含金量不一样：
* 1吨需要1个人开采，少于这个人数则一点都无法开采，大于或等于则可以开采该金矿所有资源
*
* 解：
*   设金矿的个数为n，每一座金矿的含金量gold[n]，每一座金矿的开采人数为solders[n]
*   设部队人数为s
*
*   设方程为F(n,s) 结果是在n个金矿和s位士兵的情况下，开采的最多的金矿数量
*
* 限制条件：
*   1.如果不能凑够这个金矿的开采人数，那么这个金矿就无法开采，一点都不能采
*   2.如果能够凑够人数，那么该金矿所有资源都能被开采出来，一点都不剩
*   3.一个人只能挖一个矿，被分配到a矿，就不能再去b矿或者其他矿挖
*
* 边界条件：
*       最前面的n是数量个数，从1开始数。solders[n]中的n是下标，从0开始数
*   情况1：只有1个矿，开采这个矿所需要的人数大于部队现有人数，则一点都无法开采
*       n <= 1, solders[n] > s, F(n,s) = 0
*   情况2：只有一个矿，开采这个矿所需要的人数小于或等于部队现有人数，则可以完全开发完这个矿
*       n <= 1, solders[n] <= s, F(n,s) = gold[n]
*   情况3：金矿数量不只一个，有些矿必定是因为人数不够开采不了，则尽可能在所有能开采的矿中达到开采利益最大化
*       n > 1, solders[n] > s, F(n,s) = F(n-1,s)
*   情况4：金矿数量不只一个，每一座矿的开采需求人数都小于部队现有人数，如何将利益最大化，最后一座挖不挖，不挖的话就在剩余的当中挖，
*         挖的话就需要再考虑挖完之后剩下的人如何在剩余的矿中选择挖
*       n > 1, solders[n] <= s, F(n,s) = Max( F(n-1,s), F(n-1, w-solders[n-1]) + gold[n-1] )
*
* */
//金矿矿藏与对应开采人数
let solders = 10 //所拥有的资源
let goldResource = [
    {
        gold:500, //所收到的效益
        solders:5 //资源的消耗情况
    },
    {
        gold:300,
        solders:3
    },
    {
        gold:400,
        solders:4
    },
    {
        gold:200,
        solders:2
    },
    {
        gold:350,
        solders:4
    },
]

function mining(goldResource,solders){
    let goldNumber = goldResource.length //黄金矿的数量
    let projectInit = [] //初始方案或上一次方案
    let projectResult = [] //动态的最新方案
    projectInit.length = projectResult.length = solders
    projectInit.fill(0) //往方案中填充值
    projectResult.fill(0) //往方案中填充值
    console.log("projectInit是"+projectInit)
    console.log("projectResult是"+projectResult)

    //先随便在可以挖的金矿中挑选一个开采，剩下的金矿都基于这初始方案而改动
    for(let s = 0; s <= solders; s++){ //s表示挖矿的人数
        projectInit[s] = goldResource[0].solders > s ? 0 : goldResource[0].gold
        //初始挖到的金矿 = 如果下标为第0位的金矿所需人数大于部队现有人数，则为0，否则则为下标第0位的金矿矿藏量
    }

    //这是剩余金矿的挖矿情况
    //外层循环是遍历每一座矿，内层循环是在每遍历到一座矿的时候，进入比对开采该矿的人数，即第0座0人，第0座1人，直到第0座10人（当前给定人数上限是10），
    //然后进行第二次外层遍历第1座矿，进入内层循环遍历比对开采人数，第1座0人，第1座1人，直到第1座10人的开采情况，以此类推
    for(let i = 0; i < goldNumber; i++){ //对每一座金矿进行遍历，就算从被挖过的第0座矿开始也没啥影响
        for(let s = 0; s <= solders; s++){ //对挖矿的人数遍历，循环中的循环，比对挖当前第i座所需要的人数
            if(goldResource[i].solders > s){ //如果人数不够，那么这第i座矿就无法开采，就用之前一次的挖矿的最优方案作为这一次挖完之后的最新结果
                projectResult[s] = projectInit[s] //将上一次的最优挖矿情况赋值给当前最优情况
            }else{ //人够的情况
                let gold = goldResource[i].gold + projectInit[s - goldResource[i].solders]
                //挖到的金矿 = 第i座矿的黄金 + 之前挖完矿的最优结果（减去挖完第i座矿之后，剩下的人数可以开采最多的矿）

                projectResult[s] = Math.max(projectInit[s],gold) //在之前的最优挖矿结果，和当前挖到的黄金结果中，挑选二者中较多的作为最新结果
            }
        }
        projectInit = [].concat(projectResult)
        //每挖完一座，就对当前结果进行更新，用于挖下一座时的对比参照，挖下一座时，这就成为"上一次"的最优结果
    }
    console.log("projectInit是"+projectInit)
    console.log("projectResult是"+projectResult)
    console.log("projectResult[s]是"+projectResult[solders])
    console.log("projectInit[s]是"+projectInit[solders])

    return projectResult[solders] //循环完全部矿之后，将对应的挖矿人数 在最终的最优结果中 所对应的矿量 返回出来
    //不好想的话，在Excel表格中自己填写，或想想老师的表格
}
mining(goldResource,solders)